/**
 * k个一组翻转链表
 *
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 *
 * 示例 2：
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 *
 * 提示：
 * 链表中的节点数目为 n
 * 1 <= k <= n <= 5000
 * 0 <= Node.val <= 1000
 *
 * 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
 */

/**
 * 我感觉的话这题是不是和上一题两两交换节点是一样的思路, 只不过是将两个节点换成了
 * 不确定的节点数, 但这好办呀, 我们只需要将这 k个节点的链表反转一下就可以了, 我们可以用头插法,
 * 或者我们直接弄四个节点硬核弄反转
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 *
 */

public class Main {
    public ListNode reverseKGroup(ListNode head, int k) {

        // 创建虚拟节点
        ListNode newHead = new ListNode(0);
        newHead.next = head;

        // 定义打工节点, 现在的功能是算出链表的长度
        ListNode cur = newHead.next;

        int n = 0;

        // 计算链表长度
        while (cur != null) {
            cur = cur.next;
            n++;
        }

        // 因为我们是 k 个一组分的, 所以我们要求出一共有几组需要反转链表
        n /= k;

        // 重新分配任务, 这次的任务是帮我们记录每个反转链表的前一个节点, 用作记录
        cur = newHead;

        // n 组循环
        for (int i = 0; i < n; i++) {

            // 这里我们我们需要记录下开始反转的节点, 这个节点是跟着反转不断向后面移动的,
            // 这样我们就可以得到后面的需要头插的节点
            ListNode node = cur.next;

            // 因为我们的头结点是不用尾插的, 所以是 k - 1 次循环
            for (int j = 0; j < k - 1; j++) {

                // 定义出两个节点
                // node -> tmp1 -> tmp2
                ListNode tmp1 = node.next;
                ListNode tmp2 = tmp1.next;

                // 我们进行头插, 记住 node 在向后移动, 用来确定后面需要头插的节点位置
                // tmp1 -> node -> tmp2;

                // 注意这里不能使用 tmp1.next = node
                // 因为是头插在 cur 后面的, 而 node 是跟随着向后移动的
                tmp1.next = cur.next;
                cur.next = tmp1;
                node.next = tmp2;

            }

            // 这里要更新 cur 节点, 这是头插每组的虚拟节点, 所以也要更新, 记得是头结点的前一个节点
            cur = node;
        }

        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Main test = new Main();
        test.reverseKGroup(node1, 2);
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}